翻訳と辞書 Words near each other ・ Boundary, Derbyshire ・ Boundary, Leicestershire ・ Boundary, Staffordshire ・ Boundary, Washington ・ Boundary-incompressible surface ・ Boundary-Layer Meteorology ・ Boundary-Similkameen ・ Boundary-value analysis ・ Boundary-Waneta Border Crossing ・ Boundary-work ・ Boundaryless organization ・ Bounded Choice ・ Bounded complete poset ・ Bounded deformation ・ Bounded emotionality ・ Bounded expansion ・ Bounded function ・ Bounded growth ・ Bounded inverse theorem ・ Bounded mean oscillation ・ Bounded operator ・ Bounded pointer ・ Bounded quantification ・ Bounded quantifier ・ Bounded rationality ・ Bounded Retransmission Protocol ・ Bounded set ・ Bounded set (topological vector space) ・ Bounded Type ・ Bounded type (mathematics) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Bounded expansion ： ウィキペディア英語版 Bounded expansion In graph theory, a family of graphs is said to have bounded expansion if all of its shallow minors are sparse graphs. Many natural families of sparse graphs have bounded expansion. A closely related but stronger property, polynomial expansion, is equivalent to the existence of separator theorems for these families. Families with these properties have efficient algorithms for problems including the subgraph isomorphism problem and model checking for the first order theory of graphs. ==Definition and equivalent characterizations== A ''t''-shallow minor of a graph ''G'' is defined to be a graph formed from ''G'' by contracting a collection of vertex-disjoint subgraphs of radius ''t'', and deleting the remaining vertices of ''G''. A family of graphs has bounded expansion if there exists a function ''f'' such that, in every ''t''-shallow minor of a graph in the family, the ratio of edges to vertices is at most ''f''(''t'').〔.〕 Equivalent definitions of classes of bounded expansions are that all shallow minors have chromatic number bounded by a function of ''t'',〔 or that the given family has a bounded value of a ''topological parameter''. Such a parameter is a graph invariant that is monotone under taking subgraphs, such that the parameter value can change only in a controlled way when a graph is subdivided, and such that a bounded parameter value implies that a graph has bounded degeneracy.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bounded expansion」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.